The present invention is related to method and apparatus for improving flows of video data. More particularly the present invention is directed to method and apparatus for smoothing data at a source and coordinating a data rate allocation provided by a transport medium such as a data network.
Video traffic is an increasingly important component of the workload of computer networks. Because video is so data intensive it is commonplace to use compression techniques to reduce the volume of data that must be transferred in a transmission of video. The desired quality of the video to be delivered to a receiver varies widely, depending on the application, the potential cost to a user, and the network infrastructure that is available for transporting the video. As a result, there is a relatively large class of applications that can tolerate some variability in the perceived quality of the video, including video teleconferencing, interactive training, low-cost information distribution such as news, and even some entertainment video. Especially for this class of applications, the compressed video sources may be rate adaptive, that is, by adjusting the video encoding parameters so as to be responsive to the conditions in the network it is possible to dynamically modify the source rate. One parameter particularly suitable to the task of rate adaptation is the quantization parameter.
Transporting video over Asynchronous Transfer Mode (ATM) networks has been an active area of research. The methods proposed for transport of compressed video span the spectrum of services offered by ATM networks: Constant Bit Rate (CBR), Variable Bit Rate (VBR), Available Bit Rate (ABR) and Unspecified Bit Rate (UBR). The very nature of video data has an impact on the effectiveness of any one of these ATM services. For example, compressed video is inherently bursty with data rate fluctuations happening over multiple time scales due to the fluctuations in the amount of data necessary to adequately represent the compressed frame(s) of video data. Since a compressed video source is bursty, the use of constant bit rate (CBR) transport requires the use of a local buffer for smoothing. The advantage of CBR transport is that it makes admission control simple. However, there is no attempt to exploit any multiplexing gains possible with the original bursty traffic sources. In unrestricted (or open-loop) VBR transport, the inherently bursty traffic from the coder is transported over the real-time VBR service class, thereby potentially providing greater multiplexing gain than with CBR.
Among the promising approaches for adapting to the short-term fluctuations in the rate required for video are Renegotiated CBR (RCBR), and feedback-based congestion control. U.S. patent application Ser. No. 08/825,988, entitled "A Method and Apparatus for Supporting Compressed Video with Explicit Rate Congestion Control" and filed on Apr. 4, 1997, (assigned to the assignee of the present invention) attempts to achieve the goals of increasing the multiplexing gain through frequent negotiation for bandwidth between the source and the network. The approach attempts to be responsive to the needs of the video data source, while at the same time relying on the adaptation of source rates to match bandwidth available in the network. The scheme uses congestion control mechanisms described for ATM's ABR service, referred to as explicit rate-based congestion control (examples of which are described in "ATM Forum Traffic Management Specification Version 4.0, Draft Specification ATM Forum/95-0013R11, ATM Forum March 1996 and "A Efficient Rate Allocation Algorithm for ATM Networks Providing Max-Min Fairness", Kalampoukas, et al., Proceedings of 6th IFIP International Conf. on High Performance Networking, HPN '95, Spain Sep. 11-15, 1995). This congestion control mechanism provides rate negotiation while maintaining low queuing delays in the network.
In application number '988, the response of the video source to insufficient bandwidth available from the network was to reduce the source rate by modifying the quantization value. The explicit mechanism to limit the degradation in the quality of the video below a minimum was based on a minimum cell rate (MCR) being guaranteed for the connection at the time it was setup. The admission control was relatively simple, based on the sum of the MCR values for all connections being available. The mechanisms did not make any further attempts to manage the quality degradation. It is believed that there is varying tolerance to alteration in the quality, depending on the video content (e.g., a teleconference video may be able to tolerate a grater quality degradation than entertainment video) and the scheme suggested in application '988 may be applicable in many situations. Nevertheless, it is believed that there are many circumstances in which the reduction in the source quality that is imposed by altering the quantization parameter in response to the feedback received from the network is either less tolerable or intolerable. It would be beneficial if there existed techniques that could be implemented at the source that would aid in significantly reducing this degradation of quality.
It would also be beneficial to provide a mechanism at the source which facilitates multiplexing of sources along the network links.
Multiplexing gain may be achieved as a result of overlapping "peaks" and "valleys" of the different sources of video on a link at a given time. The aggregate flows tend to be less bursty than the individual flows. The larger the number of simultaneously active flows, the higher the potential for multiplexing gain.
If an individual source is less bursty, then it is easier to support that flow by allocating a lower rate to the flow. As indicated above, compressed video is bursty over multiple time scales: at the individual frame level, possibly due to the compression algorithm and its periodic nature; at the scene level, due to changing activity and detail within a given scene; and finally between scenes, due to the different scene contents. It would be beneficial then to achieve a multiplexing gain using the explicit rate mechanisms both at the scene-level and the between-scene time scales. Algorithms that smooth the traffic from an individual video source might make it more predictable over a short time. Smoother traffic could allow source rate allocation to be made more accurately and easily over this short time scale.
There has been considerable work examining the effectiveness of smoothing of stored video. Examples include, "A Scheme for Smoothing Delay Sensitive Traffic Offered to ATM Networks", Ott et al., Proceedings of IEEE Infocom 1992, pp. 776-785, May 1992, and "Supporting Stored Video: Reducing Rate Variability Smoothing", Salehi, et al., Proceedings of the ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, pp. 222-231, May 1996. These require knowledge of the sequence of frame rates over a reasonably long window, to find the smoothing function that minimizes the overflow and underflow probability of the buffer at the source, while determining the longest piece-wise constant rate to present to the network.